L2-049 鱼与熊掌

题目 L2-049 鱼与熊掌

思路分析

代码实现

直接用set写只能13/25

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,-1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
/*
给定 n 个人对 m 种物品的拥有关系。
对其中任意一对物品种类（例如“鱼与熊掌”），
请你统计有多少人能够兼得？
*/

vector<set<int>> people;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;
	people.resize(n+1);
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		int pz;
		while(k--){
			cin>>pz;
			people[i].insert(pz);
		}
	}

	int q;cin>>q;
	while(q--){
		int a,b;cin>>a>>b;
		int cnt=0;
		for(auto p:people){
			if(p.count(a) && p.count(b)){
				cnt++;
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}

换个角度（倒排索引） 从物品入手 存储每个物品的拥有者有哪些 然后对查询物品找交集

21/25

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]= {-1,0,-1,0},dy[4]= {0,1,0,-1};
const int inf = 0x3f3f3f3f;
/*
给定 n 个人对 m 种物品的拥有关系。
对其中任意一对物品种类（例如“鱼与熊掌”），
请你统计有多少人能够兼得？
*/

unordered_map<int,unordered_set<int>> items;

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;

	for(int i=1; i<=n; i++) {
		int k,item;
		cin>>k;

		while(k--) {
			cin>>item;
			items[item].insert(i);
		}
	}

	int q;
	cin>>q;
	while(q--) {
		int a,b;
		cin>>a>>b;

		const auto& seta = items[a];
		const auto& setb = items[b];
		if(seta.size()>setb.size()) {
			swap(a,b);
		}

		int cnt=0;
		for(auto p:items[a]) {
			if(items[b].count(p)) {
				cnt++;
			}
		}

		cout<<cnt<<endl;
	}

	return 0;
}

极端数据（比如一个物品有几万人拥有）导致哈希查找效率下降或者 cache miss

使用vector 排序后，两指针线性扫交集

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,-1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

unordered_map<int, vector<int>> items;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		int k, item;
		cin >> k;
		while (k--) {
			cin >> item;
			items[item].push_back(i);
		}
	}

	for (auto& people : items) {
		sort(people.second.begin(), people.second.end());
	}

	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		const auto& pa = items[a];
		const auto& pb = items[b];
		int cnt = 0;
		int i = 0, j = 0;
		while (i < pa.size() && j < pb.size()) {
			if (pa[i] == pb[j]) {
				++cnt;
				++i;
				++j;
			} else if (pa[i] < pb[j]) {
				++i;
			} else {
				++j;
			}
		}
		cout << cnt << '\n';
	}

	return 0;
}

同类题型

视频讲解

⬅️ L2-048 寻宝图 🏠 00-天梯赛 ➡️ L2-050 懂蛇语